﻿//525.连续数组
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        hash[0] = -1;

        int sum = 0, ret = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            sum += nums[i] == 0 ? -1 : 1;
            if (hash.count(sum)) ret = max(ret, i - hash[sum]);
            else hash[sum] = i;
        }
        return ret;
    }
};

//1314.矩阵区域和
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
    {
        int row = mat.size(), col = mat[0].size();
        vector<vector<int>> dp(row + 1, vector<int>(col + 1)), answer(row, vector<int>(col));
        for (int i = 1; i <= row; i++)
        {
            for (int j = 1; j <= col; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i - 1][j - 1] - dp[i - 1][j - 1];
            }
        }

        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                int x1, y1, x2, y2;
                x1 = min(row - 1, i + k);
                y1 = min(col - 1, j + k);
                x2 = max(0, i - k);
                y2 = max(0, j - k);
                answer[i][j] = dp[x1 + 1][y1 + 1] - dp[x2][y1 + 1] - dp[x1 + 1][y2] + dp[x2][y2];
            }
        }

        return answer;
    }
};

//931.下降路径最小和
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
        for (int i = 0; i <= n + 1; i++)
        {
            dp[0][i] = 0;
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }

        int ans = dp[n][1];
        for (int i = 2; i <= n; i++)
        {
            ans = min(ans, dp[n][i]);
        }

        return ans;
    }
};